1. Field of the Invention
This invention relates generally to communication networks, and more particularly to a packet-switching communication network with different grades of service and method of design.
2. Description of the Related Art
Recently developed multimedia communication networks are expected to handle various kinds of information, such as voice, image, and data information, which have different demands of grade of service. Conventional network design methods are not particularly useful with respect to these kinds of networks because such conventional methods often times adopt an overall average delay as a design constraint to optimize a cost function.
More particularly, in designing packet switching networks, a conventional design criterion for determining capacity assignments for each link formed between nodes in a network has been network average delay. The network average delay is determined based on an average packet delay averaged over all link delays in the network for obtaining a network performance measure. Specifically, the average packet delay T is represented by ##EQU1## where ##EQU2## and .gamma..sub.i : packet rate loaded on path i Z.sub.i : average packet delay on path i
.lambda..sub.j : packet rate on link j PA1 T.sub.j : average delay of link j.
See, for example, Kleinrock, QUEUEING SYSTEMS Volume II: Computer Applications, New York: John Wiley, 1976; and Gerla and Kleinrock, "On the Topological Design of Distributed Computer Networks", IEEE Transactions on Communications, Vol. COM-25, pp. 48-60, January 1977, the disclosures of which are incorporated herein by reference.
The above conventional design approach can result in a cost-effective network from the viewpoint of a network designer or network provider. However, from a user's point of view, such a design method implies that some users of the network will experience longer delays than the network average delay T. One particular disadvantage of networks designed based on a network average delay is that when the traffic rate on a particular path is low, the delay associated with that path does not contribute significantly to the network average delay. This can result in a very large delay for the traffic on that path, a delay in excess of the average delay time T. To overcome this problem, an average end-to-end delay constraint has been adopted in place of the network average delay criterion. See, for example, Nakajima and Miyake, "Optimization of Packet-Switched Networks Under End-to-End Packet Transit Delay Constraints", Transactions of IEICE of Japan, vol. J70-A, pp. 271-277, February 1987; and Saksena, "Topological Analysis of Packet Networks", IEEE Journal on Selected Areas in Communications, vol. 7, pp. 1243-1252, October 1989, the entire disclosures of which are incorporated herein by reference.
Still another shortcoming of conventional network design methods is that there typically is no discrimination between different classes of information having different demands of grade of service. For example, multimedia communication networks are often expected to handle different kinds of information often such as voice, image, data, etc. These different kinds of information have different demands of grade of service. For example, voice and image information require rapid information transfer while computer data typically is tolerant of comparatively longer delay constraints. Moreover, different packets of the same type of information may require different grades of service. Thus, a method is needed for designing and constructing a multimedia network which can handle multimedia information based upon different demands of grade of service.
While design methods have been proposed for networks with different priority classes of traffic (e.g., demands of grade of service), such methods often suffer from many of the same drawbacks as do conventional design methods for single class service. As an example, distinct network average delays for traffic classes have been used for the design criteria as described in Maruyama and Tang, "Discrete Link Capacity and Priority Assignments in Communication Networks", IBM Journal of Research and Development, vol. 21, pp. 254-263, May 1977; and Maruyama, Fratta and Tang, "Heuristic Design Algorithm for Computer Communication Networks with Different Classes of Packets", IBM Journal of Research and Development, vol. 21, pp. 360-369, July 1977.
According to another conventional design method, the average end-to-end delay for each class of traffic is considered, as is described in Maruyama and Tang, "Discrete Link Capacity Assignment in Communication Networks", Proceedings of the Third International Computer Communication Conference (Toronto), pp. 92-97, August 1976. The disclosures of each of the above-referenced articles is incorporated herein by reference.
However, a more important network performance measure, particularly in the case of high speed networks such as a B-ISDN (Integrated Service Digital Network), is the end-to-end delay distribution for every traffic class and path in the network. For example, the delay variation for voice and image traffic should be as small as possible. Conventional approaches of network design do not fully consider such criteria.
Another important yet often overlooked design criterion relates to loss probability. In a given network, the buffers located at each node for receiving information have a fixed length. As a result, a probability exists within the network that packets of information will overflow a respective buffer such that information will be lost. The probability that information may be lost typically could be quite small, e.g., on the order of 10.sup.-6. In some cases, such a loss probability would be acceptable. For example even if a portion of a packet including voice or certain image data was lost, there would be little influence on the overall quality of the information.
On the other hand, the quality of particular types of information, e.g., image data which is differentially compressed, computer data, etc., degenerates rapidly in the event even a portion of the data is lost. Network design approaches in the past did not fully consider these types of effects of loss probability. Moreover, conventional design approaches did not consider the effects of loss probability in connection with an end-to-end delay distribution for the network.